<?php
/**
 * 难度 简单
 * 题目链接 https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
 */

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }

    function __toString()
    {
        return json_encode($this);
    }
}

class Solution {

    /**
     * 二分 + 递归
     * @param int[] $nums
     * @return TreeNode
     */
    public static function sortedArrayToBST(array $nums)
    {
        return self::bst($nums, 0, count($nums)-1);
    }

    public static function bst(array $nums, $left, $right)
    {
        if ($left > $right) {
            return null;
        }
        // 中间位置
        $mid = $left + round(($right - $left) / 2);
        // 初始化节点
        $root = new TreeNode($nums[$mid]);
        $root->left = self::bst($nums, $left, $mid - 1);
        $root->right = self::bst($nums, $mid + 1, $right);

        return $root;
    }
}

$test = [
    [[-10,-3,0,5,9]],
    [[1,3]],
];
$result = [
    [0,-3,9,-10,null,5],
    [3,1],
];

foreach ($test as $key => $value) {
    $r = Solution::sortedArrayToBST($value[0]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    echo $r . PHP_EOL;
}